2018.4.26 题是做了，每天要更新博客还是有点略麻烦

下班前才提起精神写的… （坚持坚持…）

Array - 532. 数组中的K-diff数对

题目详情

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

Example1:

输入: [3, 1, 4, 1, 5], k = 2

输出: 2

Example1:

输入: [1, 3, 1, 5, 4], k = 0

输出: 1

思路

用哈希表储存每个数字的出现次数

具体代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    let obj = {}
    let count = 0
    let len = nums.length
    
    for(let i = 0; i < len; i++) {
        if(obj[nums[i]]) {
            obj[nums[i]]++
        } else {
            obj[nums[i]] = 1
        }
    }
    for(let key in obj) {
        if(k === 0) count += obj[key] >= 2 ? 1 : 0;
        if(k > 0) {
            if(obj[String(key - 0 + k)]) {
                count += 1
            }
        }
    }
    return count
};

Array - 189. 旋转数组

题目详情

将包含 n 个元素的数组向右旋转 k 步。
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

思路

利用数组的length - k 把数组分为两半
reverse 左边和右边的数组
reverse 总数组。

举一个例子：

　　1 2 3 4 5 6 7　　如果k = 3 的话，会变成 5 6 7 1 2 3 4

　　==1 2 3 4== 5 6 7　　middle = 7 - 3 = 4，分为左边 4个数字，右边 3个数字

　　==4 3 2 1== 7 6 5　　分别把左右reverse 一下

　　==5 6 7== 1 2 3 4　　把总数组reverse 一下就会得到答案

具体代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    if(nums == null || nums.length == 0 || k % nums.length == 0) return
    
    let len = nums.length
    let turn = k % len
    let mid = len - turn
    
    swap(nums, 0, mid - 1)
    swap(nums, mid, len - 1)
    swap(nums, 0, len - 1)
};
function swap(arr, s, e) {
    console.log(arr, s, e)
    let temp
    while(s < e) {
        temp = arr[s]
        arr[s] = arr[e]
        arr[e] = temp
        s++
        e--
    }
}

Array - 665. 非递减数列

题目详情

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的：对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

Example:

输入: [4,2,3]

输出: True

Example:

输入: [4,2,1]

输出: False

思路

这个题目关键在于，当遇见一个 nums[i] > nums[i+1] 的情况，我们是把 nums[i]降为nums[i+1] 还是把nums[i+1]升为nums[i]
　来看一下两种情况：
- 　a. 1 3 ==5 4== 6 7 –> 1 3 ==4 4== 6 7
- 　当遇到5 > 4 的情况，这里因为4比5之前的所有数字都大，所以可以把5 降为4。
- 　b. 1 4 ==5 3== 6 7 –> 1 4 ==5 5== 6 7
当遇到5 > 3 的情况，这里3比5之前的4小，所以没有选择，只能把3 升为5。
当需要第二次改动的时候，可以直接返回false，不需要把剩下的array走完。

具体代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    let boo = true
    
    for(let i = 1, len = nums.length; i < len - 2; i++) {
        if(nums[i] > nums[i + 1]) {
            if(boo) {
                return false
            } else if (nums[i + 1] < nums[i - 1] && nums[i] < nums[i + 2]) {
                console.log(nums)
                nums[i + 1] = nums[i]
                boo = true
            } else {
                nums[i] = nums[i + 1]
                boo = true
            }
        }
    }
    return true
};